Homework (Week 8)
Table of Contents
Submission: Due on Friday, 29th of July, 11am Sydney Time. Please submit using the CSE Give System either online or via this command on a CSE terminal:
give cs3151 hw7 hw7.pdf
Late submissions are accepted up to five days after the deadline, but at a penalty: 5% off your total mark per day.
1 Process algebra (5 points)
We saw a large number of algebraic laws of CCS this Wednesday. Here are some more proposed laws. Briefly discuss the merits of each proposed law, and whether you think it should be accepted. If you think it should be accepted, give an informal intution for why; if you think not, give a concrete example where it has absurd consequences.
a) \(P \mathrel{|} P = P\)
b) \(P \setminus b \setminus b = P \setminus b\)
c) \((a. P) | (a.Q) = a.(P|Q)\)
2 Ricart-Agrawala Algorithm (4 points)
Pseudocode of the Ricart-Agrawala Algorithm is:
a) Suppose that we exchanged the lines p8 and p9–p11 in Main, i.e. \(\textsf{requestCS} \leftarrow \textsf{false}\) now executes after the for loop (instead of executing before the for loop). Suppose furthermore that it's possible for \(\textbf{Receive}\) to preempt \(\textbf{Main}\) at these locations. Provide an example that illustrates why the modified algorithm is no longer correct.
b) In \(\textbf{Receive}\), can the statement \(\textsf{p2:}\ \textsf{highestNum} \leftarrow \textsf{max}(\textsf{highestNum}, \textsf{requestNum})\) be replaced by \(\textsf{p2:}\ \textsf{highestNum} \leftarrow \textsf{requestNum}\)? Why? Justify your answer and provide an example.
In both parts of this question, you can sketch diagrams in addition to textual explanations. However, if your textual explanations are clear, such diagrams might be unnecessary.
3 Token-Passing (4 points)
Pseudocode of the Ricart-Agrawala Token-passing Algorithm is:
a) In node \(i\), can the value of \(\textsf{requested}[j]\) be less than the value of \(\textsf{granted}[j]\) for \(j \neq i\)? Why? Justify your answer.
b) In node \(i\), can the value of \(\textsf{requested}[j]\) be greater than the value of \(\textsf{granted}[j]\) for \(j \neq i\)? Why? Justify your answer.